|
In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to drop edges from the graph to break the cycles. A feedback arc set (FAS) or feedback edge set is a set of edges which, when removed from the graph, leave a DAG. Put another way, it's a set containing at least one edge of every cycle in the graph. Closely related are the feedback vertex set, which is a set of vertices containing at least one vertex from every cycle in the directed graph, and the minimum spanning tree, which is the undirected variant of the feedback arc set problem. A minimal feedback arc set (one that can not be reduced in size by removing any edges) has the additional property that, if the edges in it are reversed rather than removed, then the graph remains acyclic. Finding a small edge set with this property is a key step in layered graph drawing.〔.〕〔.〕 Sometimes it is desirable to drop as few edges as possible, obtaining a minimum feedback arc set, or dually a maximum acyclic subgraph. This is a hard computational problem, for which several approximate solutions have been devised. == Example == As a simple example, consider the following hypothetical situation, where in order to achieve something, certain things must be achieved before other things: * Your goal is to get the lawnmower. * George says he will give you a piano, but only in exchange for a lawnmower. * Harry says he will give you a lawnmower, but only in exchange for a microwave. * Jane says she will give you a microwave, but only in exchange for a piano. We can express this as a graph problem. Let each vertex represent an item, and add an edge from A to B if you must have A to obtain B. Unfortunately, you don't have any of the three items, and because this graph is cyclic, you can't get any of them either. However, suppose you offer George $100 for his piano. If he accepts, this effectively removes the edge from the lawnmower to the piano, because you no longer need the lawnmower to get the piano. Consequently, the cycle is broken, and you can trade twice to get the lawnmower. This one edge constitutes a feedback arc set. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Feedback arc set」の詳細全文を読む スポンサード リンク
|